package com.company.剑指offer每日刷题.普通版;

/**
 * 剑指 Offer 46. 把数字翻译成字符串
 * 给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
 * 示例 1:
 *
 * 输入: 12258
 * 输出: 5
 * 解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
 * 提示：
 *
 * 0 <= num < 231
 * */
public class TranslateNum {

    /**
     * 方法：动态规划
     * 思路：
     *      定义：
     *          1.假设nums有k位,0<=i<= k,nums的前i+1个位数有dp[i]种翻译方式。
     *          2.令nums[i]为nums的第i位数
     *      初始条件：
     *          dp[0] = 1;
     *      状态转移方程：
     *             当nums[(i-1):i]可以连着翻译： dp[i] = dp[i-1] + dp[i-2]
     *             当nums[(i-1):i]不可以连着翻译：dp[i] = dp[i-1]
     *
     * */
    public int translateNum(int num) {
        char[] nums = String.valueOf(num).toCharArray();
        int dp[] = new int[nums.length +1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i < dp.length; i++) {
            if( ('1' == nums[i-2] && '0' <= nums[i-1] && nums[i-1] <= '9')||('2' == nums[i-2] && '0' <= nums[i-1] && nums[i-1] <= '5') )dp[i] = dp[i-2] + dp[i-1];
            else dp[i] = dp[i-1];
        }
        return dp[nums.length];
    }
    /**
     * 优化：
     *      1.因为这里dp[i] 的计算，最多只用到了 dp[i-1] 和 dp[i-2]，所以可以不用保存所有的值
     *      2. '2'和'3' 组成 的 '23'可以 直接 用String 的 compareTo 来与 "10" 和"25"比较，所以也不用生成字符数组 nums
     * 反思：这个题思路想出来了，但是在实现代码阶段花了很多时间，原因是没有在一开始设计的时候，过早地并过分重点地关注边界问题，导致忽略了动态规划的本质。
     *          下次应当先写出骨干的代码，边界问题可以根据写得代码，结合实际情况去考量和解决
     * */
    public int translateNum1(int num) {
        String s = String.valueOf(num);
        int num1 =1 ,num2=1,num3 = 1;
        for (int i = 2; i <= s.length(); i++) {
            if("10".compareTo(s.substring(i-2,i)) <= 0 && "25".compareTo(s.substring(i-2,i)) >=0){
                num3 = num1 + num2;
                num1 = num2;
                num2 = num3;
            } else num3 = num2;
        }
        return num3;
    }

    public static void main(String[] args) {
        TranslateNum obj = new TranslateNum();
        int i = obj.translateNum1(18822);
        System.out.println(i);
    }
}
